// 给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

// 具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

//  

// 示例 1：

// 输入："abc"
// 输出：3
// 解释：三个回文子串: "a", "b", "c"

// 来源：力扣（LeetCode）
// 链接：https://leetcode-cn.com/problems/palindromic-substrings
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include<bits/stdc++.h>
#include<string>
#include<vector>
#include<unordered_set>
#include<unordered_map>
#include<set>
#include<queue>
#include<stack>
using namespace std;

// 看了题解。动态规划

// 执行用时：
// 16 ms
// , 在所有 C++ 提交中击败了
// 44.54%
// 的用户
// 内存消耗：
// 7.4 MB
// , 在所有 C++ 提交中击败了
// 49.48%
// 的用户

class Solution {
public:
    int countSubstrings(string s) {
        // 初始化dp,默认均不为回文子串
        vector<vector<bool>> dp(s.size(),vector<bool>(s.size(),false));
        // 从后往前遍历
        int res = 0;
        for(int i=s.size()-1;i>=0;i--){
            for(int j=i;j<s.size();j++){
                // 单个字符/两个字符
                if(j-i<=1){
                    if(s[i]==s[j]){
                        res++;
                        dp[i][j]=true;
                    }
                }
                else{
                    // 如果i i+1 ... j-1 j,两头相等且中间为回文，则ij为回文
                    if(s[i]==s[j]&&dp[i+1][j-1]){
                        res++;
                        dp[i][j] = true;
                    }
                }

            }
        }
        return res;
    }
};